/*
 * Project: Sudoku Hint Engine for Android
 * Copyright (C) 2010-2013 Emanuel Moecklin
 * 
 * Available under the terms of the Lesser General Public License (LGPL)
 */
package com.onegravity.sudoku.solver.rules.als;

import java.util.ArrayList;
import java.util.BitSet;
import java.util.Collection;
import java.util.HashMap;
import java.util.List;
import java.util.Map;
import java.util.TreeSet;

import com.onegravity.sudoku.solver.HintResource;
import com.onegravity.sudoku.solver.R;
import com.onegravity.sudoku.solver.accumulator.HintsAccumulator;
import com.onegravity.sudoku.solver.accumulator.StopHintProductionException;
import com.onegravity.sudoku.solver.core.IndirectHint;
import com.onegravity.sudoku.solver.core.IndirectHintProducer;
import com.onegravity.sudoku.solver.data.Block;
import com.onegravity.sudoku.solver.data.Cell;
import com.onegravity.sudoku.solver.data.Column;
import com.onegravity.sudoku.solver.data.ExtraRegionExtended;
import com.onegravity.sudoku.solver.data.Grid;
import com.onegravity.sudoku.solver.data.Region;
import com.onegravity.sudoku.solver.data.Row;
import com.onegravity.sudoku.solver.util.Permutations;

/**
 * Almost Locked Candidates:
 * - degree 2 = bivalue cells
 * - degree 3 = trivalue cells
 * - degree 4 = quadvalue cells
 * Code supports higher degree but even degree 4 can hardly be found
 * @author Emanuel Moecklin
 */
public class ALCProducer implements IndirectHintProducer {

	private final int degree;

	private final BitSet unionPotentials = new BitSet();				// temporarily used to collect ALS potentials
	private final List<Cell> alsCells = new ArrayList<Cell>();			// temporarily used to collect ALS cells
	
	public ALCProducer(int degree) {
		this.degree = degree;
	}
	
    public void getHints(Grid grid, HintsAccumulator accu) throws StopHintProductionException, InterruptedException {
        if (grid.hasExtraRegions()) {
            getHints(grid, Block.class, ExtraRegionExtended.class, accu);
            getHints(grid, Row.class, ExtraRegionExtended.class, accu);
            getHints(grid, Column.class, ExtraRegionExtended.class, accu);
        }
        getHints(grid, Block.class, Column.class, accu);
        getHints(grid, Block.class, Row.class, accu);
    }

    private <S extends Region, T extends Region> void getHints(Grid grid, Class<S> regionType1, Class<T> regionType2, HintsAccumulator accu)
    												  throws StopHintProductionException, InterruptedException {

    	// (1) find two intersecting regions
    	for (Region region1:grid.getRegions(regionType1)) {
        	for (Region region2:grid.getRegions(regionType2)) {
                if (Thread.interrupted()) throw new InterruptedException();
                if (region1.crosses(region2)) {

                	// (2) find two identical ALS in the relative complements of the two regions
                	List<Cell> region1Cells = region1.getCellSet();
                    List<Cell> region2Cells = region2.getCellSet();
                    // create relative complement of region 2 in region 1
                    List<Cell> complementCells1 = region1.getCellSetClone();
                    complementCells1.removeAll(region2Cells);
                    // create relative complement of region 1 in region 2
                    List<Cell> complementCells2 = region2.getCellSetClone();
                    complementCells2.removeAll(region1Cells);
                    // find ALS in the two complements
                    List<ALS> allALS1 = findALS(grid, region1, complementCells1);
                    List<ALS> allALS2 = findALS(grid, region2, complementCells2);
                    for (ALS als1:allALS1) {
                    	BitSet candALS1 = als1.getPotentials();
                        for (ALS als2:allALS2) {
                        	BitSet candALS2 = als2.getPotentials();
                        	if (candALS1.equals(candALS2)) {
                        		
                        		// (3) now let's check if the ALS candidates:

                        		// (3.1) are in the intersection of the two regions
                                List<Cell> intersectingCells = region1.getCellSetClone();
                                intersectingCells.retainAll(region2Cells);
                                getUnion(unionPotentials, intersectingCells, null);
                                unionPotentials.and(candALS1);
                                if (unionPotentials.equals(candALS1)) {

                                	// (3.2) are in just one of the relative complements
                                	getUnion(unionPotentials, complementCells1, als1.getCells());
                                	unionPotentials.and(candALS1);
                                    boolean containsALSCandidates1 = (unionPotentials.cardinality()>0);
                                	getUnion(unionPotentials, complementCells2, als2.getCells());
                                	unionPotentials.and(candALS1);
                                    boolean containsALSCandidates2 = (unionPotentials.cardinality()>0);
                                    if (containsALSCandidates1 != containsALSCandidates2) {

                                    	// we found an Almost Locked Set
                                    	IndirectHint hint = null;
                                    	if (containsALSCandidates1) {
                                    		Map<Cell,BitSet> removablePotentials = getRemovablePotentials(complementCells1, candALS1, als1.getCells());
                                        	hint = new ALCHint(degree, als1, als2, removablePotentials);
                                    	}
                                    	else if (containsALSCandidates2) {
                                    		Map<Cell,BitSet> removablePotentials = getRemovablePotentials(complementCells2, candALS2, als2.getCells());
                                        	hint = new ALCHint(degree, als2, als1, removablePotentials);
                                    	}
                                    	if (hint!=null && hint.isWorth()) accu.add(hint);
                                    	
                                    }
                                }
                        		
                        	}
                        }
                    }

                }
            }
        }
    }
    
    private List<ALS> findALS(Grid grid, Region region, List<Cell> cells) throws InterruptedException {
    	List<ALS> result = new ArrayList<ALS>();
    	int nrOfCells = cells.size();
    	if (degree<2 || degree>nrOfCells+1) return result;

    	// check all permutations for an ALS
    	Permutations perm = new Permutations(degree-1, nrOfCells);
        while (perm.hasNext()) {
            if (Thread.interrupted()) throw new InterruptedException();
            int[] indicesArray = perm.nextBitNums();
            alsCells.clear();
        	unionPotentials.clear();
            boolean isALS = true;
        	for (int index:indicesArray) {
        		Cell cell = cells.get(index);
        		unionPotentials.or( cell.getPotentialValues() );
        		if (!cell.isEmpty() || unionPotentials.cardinality()>degree) {
        			isALS = false;
        			break;
        		}
        		alsCells.add(cell);
        	}
        	if (isALS && unionPotentials.cardinality()==degree) {
        		ALS als = new ALS(grid, 0, degree, new TreeSet<Cell>(alsCells), (BitSet) unionPotentials.clone(), region);
        		result.add(als);
        	}
        }
        
        return result;
    }

    private BitSet getUnion(BitSet result, List<Cell> cells, Collection<Cell> excludeCells) {
    	result.clear();
    	for (Cell cell:cells) {
    		if (cell.isEmpty() && (excludeCells==null || !excludeCells.contains(cell))) {
    			result.or(cell.getPotentialValues());
    		}
    	}
    	return result;
    }

    private Map<Cell,BitSet> getRemovablePotentials(List<Cell> cells, BitSet candidates, Collection<Cell> excludeCells) {
        // Build list of removable potentials
        Map<Cell,BitSet> removablePotentials = new HashMap<Cell,BitSet>();
        for (Cell cell:cells) {
        	if (excludeCells==null || !excludeCells.contains(cell)) {
            	BitSet tmp = (BitSet) cell.getPotentialValues().clone();
            	tmp.and(candidates);
            	if (tmp.cardinality()>0) {
                    removablePotentials.put(cell, tmp);
            	}
        	}
        }
        return removablePotentials;
    }
    
	@Override
	public String getProducerName() {
		int id = R.string.hint_pair;
		switch(degree) {
		case 2: id = R.string.hint_pair; break;
		case 3: id = R.string.hint_triple; break;
		case 4: id = R.string.hint_quad; break;
		}
    	return HintResource.getString(R.string.producer_almost_locked_candidates, HintResource.getString(id));
	}
}